package SingleLinkList;

public class MyLinklist implements SingleLinkList{

    //头节点---》 该链表中 头节点 会改变
    public LinkNode head;


    //首先单向链表有一个节点： 有data 以及 next
    static final class LinkNode{

        public int data;
        public LinkNode next;

        //  此处重载他的构造方法来 设置 data的值
        public LinkNode(int data) {
            this.data = data;
        }
    }

    public void  creat(){
        LinkNode linkNode=new LinkNode(12);
        LinkNode linkNode2=new LinkNode(23);
        LinkNode linkNode3=new LinkNode(34);
        LinkNode linkNode4=new LinkNode(45);

        linkNode.next=linkNode2;
        linkNode2.next=linkNode3;
        linkNode3.next=linkNode4;

        head=linkNode;
    }

    @Override
    public void display() {
        // 重新定义一个节点，保证head不变
        LinkNode curhead=head;
            while(curhead != null){
                System.out.print(curhead.data+" -> ");
                curhead=curhead.next;
            }
        System.out.println(" null");

    }

    @Override
    public void addFirst(int data) {
        LinkNode curhead=new LinkNode(data);
        curhead.next=this.head;
        head=curhead;

    }

    @Override
    public void addLast(int data) {
        LinkNode cur=new LinkNode(data);


        // 找到尾节点
        LinkNode curhead=head;
        while(curhead.next != null){
            curhead=curhead.next;
        }
        curhead.next=cur;
    }

    @Override
    public void addIndex(int index, int data) throws IndexIllegarlity{
        if(index<0 || index> size()){
            //抛出异常
            throw  new IndexIllegarlity(" index 异常");
        }
        else {
            if (index == 0) {
                addFirst(data);
                return ;
            }
            if(index ==size()){
                addLast(data);
                return ;
            }
            LinkNode node = new LinkNode(data);
            LinkNode cur = FindPrevIndex(index);
                node.next = cur.next;
                cur.next = node;

        }
    }

    // 找到index 前一个位置
    private  LinkNode FindPrevIndex(int index){
        LinkNode cur = head;

        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    @Override
    public boolean contains(int key) {
        LinkNode curhead=head;
        while(curhead != null){
            if(curhead.data==key){
                return true;
            }
            curhead=curhead.next;
        }
        return false;
    }

    /*@Override
    public void remove(int key) {
        LinkNode curhead=head;
        if(curhead==null){
            System.out.println(" 没有这个数字！");
            return ;
        }
            while (head != null) {
                //当第一个就是 要删除的 关键字时
                if(head.data ==key){
                    // 删除关键字
                    head=head.next;
                    break;
                }else {
                    if ((head.next).data == key) {
                        //那么当curhead 的下一个就是 关键字key时
                        head.next = (head.next).next;
                        head=curhead;
                        break;
                    }
                    head = head.next;
                }

        }

    }
*/
    @Override
    public void remove(int key) {
        // 链表是否为空
        if (this.head == null) {
            System.out.println(" 空链表！");
            return;
        }

        //当第一个就是 要删除的 关键字时
        if (this.head.data == key) {
            // 删除关键字
            head = head.next;
            return ;
        }
        //第一个不是key时，找到key的前一位
        LinkNode cur = findPrevKey(key);
        if (cur==null) {
            System.out.println("没有这个数字！！");
            return ;
        }
        LinkNode del=cur.next;
        cur.next=del.next;
    }


    // 找到 key 的前一位
    private LinkNode findPrevKey(int key){
        LinkNode cur=this.head;
        // 当cur 的next 不是null时，就说明cur不是最后一位
        while (cur.next != null) {
            //下一位的data = key 时，cur 就是 key的前一位
            if(cur.next.data==key) {
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }




    /*@Override
    public void removeAllKey(int key) {
        LinkNode curhead=head;
        if(curhead==null){
            System.out.println(" 没有这个数字！");
            return ;
        }
        while (head != null) {
                //当第一个就是 要删除的 关键字时
                if(head.data ==key){
                    // 删除关键字
                    head=head.next;
                    curhead=head;
                }else {
                    if ((head.next).data == key) {
                        //那么当curhead 的下一个就是 关键字key时

                        head.next = (head.next).next;
                    }
                    head = head.next;
                }
            }
        head=curhead;
    }*/
    @Override
    public void removeAllKey(int key) {

        if(this.head==null){
            System.out.println(" 没有这个数字！");
            return ;
        }

        LinkNode cur=head.next;
        LinkNode prev=head;
        while (cur != null) {
            // 如果cur 是要删除的关键字
            if (cur.data == key) {
                prev.next =cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur = cur.next;
            }
        }
        //当第一个就是 要删除的 关键字时 --》 如果先判断 第一个是不是key时，如果 链表中存的都是 key，那么后面就会漏掉一个第二个是key
        if(head.data ==key){
            // 删除关键字
            head=head.next;
        }
    }

    @Override
    public int size() {

        int count=0;
        LinkNode curhead=head;
        while(curhead != null){
            count++;
            curhead=curhead.next;
        }
        return count;

    }

    @Override
    public void clear() {
        /*//最简单的就是直接将head置空
        head=null;*/

        //或者遍历链表，依次置空
        LinkNode cur=head;
        while(cur!=null){
            LinkNode nextNode=cur.next;
            // 当 数据为引用数据类型时，将data置空
            // cur.data=null;
            cur.next=null;
            cur=nextNode;
        }
        head=null;
    }


    // 反转链表
    public void reverseList() {
        // 空链表
        if(head ==null){
            return ;
        }

        LinkNode cur=head.next;
        // 要将原先的头节点的next置空
        head.next=null;
        while(cur!=null){
            LinkNode nextNode=cur.next;
            cur.next=head;
            head=cur;
            cur=nextNode;
        }
    }



    // 找链表的中间节点
    public LinkNode middleNode() {
      /*  //方法一： 先遍历一遍, 算出链表中的元素个数 n ，再将 头节点移动 k/2
        LinkNode cur=head;
        int n=size()/2;
        for(int i=0;i<n;i++){
            cur=cur.next;
        }
        return cur;
*/

        // 方法二： 定义一个fast 和一个 slow，fast 2步一走；slow 1步一走

        LinkNode fast=head;
        LinkNode slow=head;

        while(fast != null && fast.next != null){
            fast=(fast.next).next;
            slow=slow.next;
        }
        return slow;
    }


    // 合并有序链表
    public LinkNode mergeTwoLists(LinkNode list1, LinkNode list2) {
    // 虚拟头节点
        LinkNode newhead =new LinkNode(-1);
    // 最新尾节点
        LinkNode curNode=newhead;

        while(list1 != null && list2!= null){
        // 比较大小
        if(list1.data <list2.data){
            curNode.next = list1;
            list1=list1.next;
        }else{
            curNode.next = list2;
            list2=list2.next;
        }
        curNode=curNode.next;
    }
        if(list1!=null){
        curNode.next=list1;
    }
        if(list2!=null){
        curNode.next=list2;
    }

        return newhead.next;

    }


    // 判断是否回文
    public boolean chkPalindrome() {
        // write code here

        if(head==null || head.next==null){
            return true;
        }

        // 找到中间值 slow
        MyLinklist.LinkNode fast=head;
        MyLinklist.LinkNode slow=head;

        while(fast != null && fast.next != null){
            fast=(fast.next).next;
            slow=slow.next;
        }

        // 将后面的数据反转
        MyLinklist.LinkNode cur=slow.next;
        while(cur!=null){
            MyLinklist.LinkNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }


        // 在从前往后 从后往前
        while(head!=slow){

            if(slow.data==head.data){
                head=head.next;
                slow=slow.next;
            }else{
                return false;
            }
            if(head.next==slow){
                return true;
            }
        }
        return true;
    }




    // 链表分割：大于x的放后面，小于放前面
    public LinkNode partition(LinkNode pHead, int x) {
        // write code here
        if(pHead==null || pHead.next==null){
            return pHead;
        }

        // 先定义2个节点，一部分用来存 x 的节点: be 相当于头节点，bs相当于尾节点
        LinkNode bs1=null;
        LinkNode bf1=null;

        LinkNode bs2=null;
        LinkNode bf2=null;

        LinkNode cur=pHead;
        // 遍历链表
        while(cur!=null){
            if(cur.data<x){
                // 插入第一个节点
                if(bs1 ==null){
                    bs1=cur;
                    bf1=cur;
                }else{
                    bf1.next=cur;
                    bf1=bf1.next;
                }
            }else{
                // 插入第一个节点
                if(bs2 ==null){
                    bs2=cur;
                    bf2=cur;
                }else{
                    bf2.next=cur;
                    bf2=bf2.next;
                }

            }
            cur=cur.next;
        }

        // 将大于x的链表的最后一个next置空
        if(bs2!=null){
            bf2.next=null;
        }

        // 遍历完 在将2链表连接起来
        // 第一个空间没数据
        if(bs1==null){
            return bs2;
        }
        // 有数据
        bf1.next=bs2;
        return bs1;
    }



    // 相交链表
    public LinkNode getIntersectionNode(LinkNode headA, LinkNode headB) {
        LinkNode cur1=headA;
        LinkNode cur2=headB;

        int count1=0;
        int count2=0;
        while(cur1!=null){
            cur1=cur1.next;
            count1++;
        }
        while(cur2!=null){
            cur2=cur2.next;
            count2++;
        }
        // 用来存储长度差
        int c=count1-count2;
        cur1=headA;
        cur2=headB;

        if(count1<count2){
            cur1=headB;
            cur2=headA;
            c=count2-count1;
        }
        // cur1存储的是 长链表
        while(c!=0){
            cur1=cur1.next;
            c--;
        }

        while(cur1 != cur2){
            cur1=cur1.next;
            cur2=cur2.next;
        }
        if(cur1 ==null ){
            return null;
        }

        return cur1;


    }




    // 判断是否存在环
}



